11.2.4 Преобразование кнф в днф и днф в кнф

1. Преобразование кнф в днф

Это преобразование проводится достаточно просто:

– Раскрыть скобки и упростить.

Пример 1:

2. Преобразование днф в кнф

Здесь возможны два варианта.

Первый вариант основан на многократном применении дистрибутивного закона дизъюнкции относительно конъюнкции п. 1.6. 8,б.

Пример 2:

Сначала распределяем , затеми, наконец, удаляем 1.

Второй вариант сложнее. Порядок действий здесь таков.

1. Взять двойное отрицание от всего выражения;

2. Используя одно отрицание и законы де Моргана, перевести исходное выражение под вторым отрицанием в КНФ (второе отрицание сохранить);

3. Перевести полученную КНФ под общим отрицанием в ДНФ – раскрыть скобки и упростить. Получим ДНФ с общим отрицанием;

4. Используя второе отрицание и законы де Моргана перевести результат предыдущего действия в КНФ.

Пример 3:

11.2.5 Доказательства равенства логических функций

Если требуется сравнить две логические функции f₁ и f₂, то следует преобразовать их или представить в виде

а) Таблиц истинности – ТИ₁ и ТИ₂;

б) СДНФ – СДНФ₁ и СДНФ₂;

в) СКНФ – СКНФ₁ и СКНФ₂;

г) Полиномов Жегалкина.

Сравнение логических функций с помощью таблиц истинности – это стандартный прием, а почему сравнение логических функций удобно проводить в совершенных формах или в форме полинома Жегалкина? Ответ прост: логическая функция может иметь много формул, ее представляющих, но совершенные формы и полином жегалкина у нее единственны.

Замечание:От СДНФ легко можно перейти к СКНФ, (а от СКНФ к СДНФ) – если СДНФ имеетkконъюнкций, то СКНФ будет иметь 2ⁿ–kдизъюнкций, гдеn– число переменных (если СКНФ имеетkдизъюнкций, то СДНФ будет иметь 2ⁿ–kконъюнкций).

Пример: Доказать, что.

1. Раскрываем скобки в левой части и упрощаем

В результате получили выражение идентичное правой части.

2. Переход к СДНФ удобно производить от ДНФ.

Вместо недостающей переменной в конъюнкциях ДНФ ставим 1, а потом заменяем ее на сумму прямого и инверсного значений этой переменной, раскрываем скобки и получаем СДНФ:

Если установить порядок входных переменных xyz,z– младшая переменная, то единичными наборами (для которых определена СДНФ) являются 7, 6, 5, 3, 1 (определяем по значениям переменных), а нулевыми наборами (для которых надо написать произведение сумм) будут 0, 2, 4, поэтому для СКНФ получаем

Не забывайте: если в СКНФ переменная без отрицания, то в соответствующем входном наборе она имеет значение 0, если с отрицанием, то 1.

3. Переход к СКНФ удобнее производить от КНФ. Здесь вместо недостающей переменной в дизъюнкции ставим 0 а затем 0 заменяем произведением прямого и инверсного значений этой переменной.

Как видим, результаты преобразований совпали, следовательно, тождество доказано.

4. По СДНФ или по СКНФ легко построить таблицу истинности (табл. 11.4).

Таблица 11.4
№	x	y	z	f
0	0	0	0	0
1	0	0	1	1
2	0	1	0	0
3	0	1	1	1
4	1	0	0	0
5	1	0	1	1
6	1	1	0	1
7	1	1	1	1

11.2.6 Разложение логических функций по переменным

В п. 11.2.1 (правила 13 (1) и (2)) показаны два варианта разложения логической функции по переменным. При разложении логической функции по всем переменным по варианту (1) получается СДНФ, а по варианту (2) – СКНФ. Реализовать эти разложения можно либо последовательно, либо параллельно. В качестве примера рассмотрим разложение функции

а) Последовательное разложение логической функции по всем переменным

Разложение по 13 (1)

Разложение по переменной x₁

Сначала определяем значение функции приx₁= 1 и получаемЗатем при x₁= 0 получаем

Подставив полученные значения функции fв выражение дляf₁, получаем

В результате разложения по x₁получили функцию

Разложение по переменной x₂

Действуя аналогично, но с функцией , получаем

Таким образом,

Разложение по переменной x₃

Получили СДНФ функции.

разложение по13 (2)

Имеем функцию .

Разложение по переменной x₁

Сначала в формулу вместоx₁подставляем 0 и получаемПриx₁= 1 получаем

Разложение по переменной x₂

Имеем

Обратите внимание на скобку , которая преобразуется впо дистрибутивному закону 8,б (см. п. 1.6).

Разложение по переменной x₃

Имеем

Здесь также применяется дистрибутивный закон 8,б п. 1.6.

Произведя перестановку переменных (как при разложении по п. 1.6.13 (1)), получаем

Получили СКНФ логической функции.

б) Параллельное разложение логической функции по всем переменным

разложение по13 (1)

Подставляя вместо переменных в формулу значения, показанные в скобках, будем иметь значения функции

После их подстановки и упрощения получим

При разложении функции по всем переменным по п. 1.6.13 (1) получили СДНФ, в соответствии с которой функция имеет значение 1 на наборах: 7, 5, 4.

Разложение по 13 (2)

Подставляя вместо переменных в формулузначения, показанные в скобках, получим значения функции, и после подстановки этих значений и упрощения будем иметь

При разложении функции по всем трем переменным по п. 1.6.13 (2) получили СКНФ, в соответствии с которой функция имеет значение 0 на наборах 0, 1, 2, 3, 6.

Как видим, результаты последовательного и параллельного разложений функции по всем переменным совпадают.

11.2.7 Вопросы для контроля

1. Приведите логические операции, используемые при формировании логических функций двух переменных (условные обозначения функций).

2. Приведите структуру таблицы истинности.

3. Приведите законы булевой алгебры:

- нуля и единицы,

- повторения,

- дополнительности,

- коммутативные,

- ассоциативные и

- дистрибутивные.

4. Приведите законы:

- поглощения,

- склеивания и

- де Моргана.

5. Покажите на примерах разложение логических функций по переменным.

6. Как доказываются тождества в булевой алгебре?